package dp;

/**
 * @Author: wangliuyang
 * @Date: 2021/8/16 19:47
 * @Description:交错字符串
 */
public class Solution_97 {
    public boolean isInterleave(String s1, String s2, String ai) {
        if (s1 == null || s2 == null || ai == null) {
            return false;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] aim = ai.toCharArray();
        if (aim.length != str1.length + str2.length) {
            return false;
        }
        boolean[][] dp = new boolean[str1.length + 1][str2.length + 1];
        dp[0][0] = true;
        for (int i = 1; i <= str1.length; i++) {
            if (str1[i - 1] != aim[i - 1]) {
                break;
            }
            dp[i][0] = true;
        }
        for (int j = 1; j <= str2.length; j++) {
            if (str2[j - 1] != aim[j - 1]) {
                break;
            }
            dp[0][j] = true;
        }
        for (int i = 1; i <= str1.length; i++) {
            for (int j = 1; j <= str2.length; j++) {

                if (

                        (str1[i - 1] == aim[i + j - 1] && dp[i - 1][j])

                                ||

                                (str2[j - 1] == aim[i + j - 1] && dp[i][j - 1])


                ) {


                    dp[i][j] = true;


                }



            }
        }
        return dp[str1.length][str2.length];
    }
}
